/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 5/28/2008
 */

#ifndef BTNODE_H
#define BTNODE_H











/*
 * Node.h
 *
 *  Created on: May 21, 2012
 *      Author: Zorayr Khalapyan
 */

#ifndef NODE_H_
#define NODE_H_

#include "RecordFile.h"
#include "PageFile.h"

template<class T>

class Node {
public:

	Node();
	Node(int key, T value);

	int read(const char* buffer, int offset);
	int write(char* buffer, int offset);

	int getKey();
	T getValue();

	void setNext(Node<T>* node);
	Node<T>* getNext();

	void setPrevious(Node<T>* node);
	Node<T>* getPrevious();

	static size_t getNodeSize();

	virtual ~Node();

private:

	int key;
	T value;

	Node<T> *next, *previous;

};

#endif /* NODE_H_ */





/**************************************************************/


#ifndef NODE_C_
#define NODE_C_

/*
 * Node.cpp
 *
 *  Created on: May 21, 2012
 *      Author: Zorayr Khalapyan
 */

#include <cstring>

template<class T>
Node<T>::Node() {
	next = 0;
	previous = 0;
}

template<class T>
Node<T>::Node(int key, T value) {
	this->key = key;
	this->value = value;
}

template<class T>
int Node<T>::write(char* buffer, int offset){

	memcpy(&buffer[offset], &key, sizeof(int));
	offset += sizeof(int);

	memcpy(&buffer[offset], &value, sizeof(T));
	offset += sizeof(T);

	return offset;
}

template<class T>
int Node<T>::read(const char* buffer, int offset){

	//Read in the stored key.
	memcpy(&key, &buffer[offset], sizeof(int));
	offset += sizeof(int);

	//Read in the stored value.
	memcpy(&value, &buffer[offset], sizeof(T));
	offset += sizeof(T);

	return offset;

}

template<class T>
int Node<T>::getKey() {
	return key;
}

template<class T>
T Node<T>::getValue(){
	return value;
}

template<class T>
size_t Node<T>::getNodeSize(){
	return sizeof(int) + sizeof(T);
}

template<class T>
void Node<T>::setNext(Node<T>* node) {
	this->next = node;
}

template<class T>
Node<T>* Node<T>::getNext() {
	return next;
}

template<class T>
void Node<T>::setPrevious(Node<T>* node) {
	this->previous = node;
}

template<class T>
Node<T>* Node<T>::getPrevious() {
	return previous;
}

template<class T>
Node<T>::~Node() {
	//Nothing to cleanup.
}


#endif /* NODE_C_ */


/**************************************************************/





/*
 * DoubleLinkedList.h
 *
 *  Created on: May 21, 2012
 *      Author: Zorayr Khalapyan
 */

#ifndef DOUBLYLINKEDLIST_H_
#define DOUBLYLINKEDLIST_H_

#include "PageFile.h"
#include "RecordFile.h"

template <class T>

class DoublyLinkedList {

public:

	DoublyLinkedList();
	DoublyLinkedList(int capacity);

	int read(const char* buffer, int offset = 0);
	int write(char* buffer, int offset = 0);

	int getSize();
	Node<T>* getHead();
	Node<T>* getTail();

	DoublyLinkedList<T>* split(int pivot);

	bool insert(int key, T value, bool force = false);
	bool insert(Node<T>* node, Node<T>* next = 0, bool force = false);
	bool insertSorted(int key, T value, bool force = false);
	bool insertSorted(Node<T>* node, bool force = false);

	bool remove(int key);
	bool remove(Node<T>* node);


	Node<T>* findBySearchKey(int searchKey);
	Node<T>* findKey(int key);
	bool keyExists(int key);

	Node<T>* findNode(Node<T>* node);
	Node<T>* getNode(int index);
	bool nodeExists(Node<T>* node);

	void setCapacity(int capacity);
	bool isFull();
	bool empty();

	void print();

	virtual ~DoublyLinkedList();

private:
	int size, capacity;
	Node<T> *head, *tail;
};

#endif /* DOUBLYLINKEDLIST_H_ */






/**************************************************************/







/*
 * DoubleLinkedList.cpp
 *
 *  Created on: May 21, 2012
 *      Author: administrator
 */

#ifndef DOUBLYLINKEDLIST_C_
#define DOUBLYLINKEDLIST_C_


#include <cstring>
#include <cstdio>
#include <iostream>

using namespace std;


template<class T>
DoublyLinkedList<T>::DoublyLinkedList() {
	size = 0;
	head = 0;
	tail = 0;

	//Capacity of 0 indicates that the capacity is infinite.
	capacity = 0;
}


template<class T>
DoublyLinkedList<T>::DoublyLinkedList(int capacity) : DoublyLinkedList() {
	this->capacity = capacity;
}



template<class T>
int DoublyLinkedList<T>::getSize() {
	return size;
}

template <class T>
bool DoublyLinkedList<T>::insert(int key, T	 value, bool force){
	return insert(new Node<T>(key, value), 0, force);
}

template <class T>
bool DoublyLinkedList<T>::insert(Node<T>* node, Node<T>* next, bool force) {

	if(!force && isFull())
		return false;

	//Prevent insertion of null nodes or duplicate keys.
	if(node == 0 || findKey(node->getKey()) != 0)
		return false;

	switch(size){
	case 0:

		head = node;
		tail = node;

		node->setNext(0);
		node->setPrevious(0);

		break;

	default:

		if(next == head){

			node->setPrevious(0);
			node->setNext(head);
			head->setPrevious(node);
			head = node;

		}else if(next == 0){

			node->setNext(0);
			node->setPrevious(tail);

			tail->setNext(node);
			tail = node;

		}else{

			node->setNext(next);
			node->setPrevious(next->getPrevious());

			node->getNext()->setPrevious(node);
			node->getPrevious()->setNext(node);
		}

		break;

	}

	size++;
	return true;
}

template <class T>
bool DoublyLinkedList<T>::insertSorted(int key, T value, bool force){
	return insertSorted(new Node<T>(key, value), force);
}

template <class T>
bool DoublyLinkedList<T>::insertSorted(Node<T>* node, bool force) {

	Node<T>* currentNode = head;

	while(currentNode != 0){

		if(node->getKey() <= currentNode->getKey()){
			return insert(node, currentNode, force);
		}

		currentNode = currentNode->getNext();
	}

	return insert(node, currentNode, force);
}

template <class T>
bool DoublyLinkedList<T>::remove(int key) {

	Node<T>* node = findKey(key);

	if(node == 0)
		return false;

	return remove(node);
}


template <class T>
bool DoublyLinkedList<T>::remove(Node<T>* node) {

	if(size == 0 || node == 0 || !nodeExists(node))
		return false;

	else if(size == 1 && head != node)
		return false;

	switch(size){
	case 1:

		head = 0;
		tail = 0;

		break;

	default:

		if(node == head){
			head = node->getNext();
			head->setPrevious(0);

		}else if(node == tail){
			tail = node->getPrevious();
			tail->setNext(0);

		}else{
			node->getPrevious()->setNext(node->getNext());
			node->getNext()->setPrevious(node->getPrevious());

		}

		break;
	}

	size--;
	delete node;
	return true;
}

template <class T>
DoublyLinkedList<T>* DoublyLinkedList<T>::split(int splitIndex){

	//Cannot split a list of size less than 1, and cannot split
	//list at the head or at the tail. Just too lazy to program
	//that part right now.
	if(size <= 1 || splitIndex == 0 || splitIndex == size){
		return 0;
	}

	Node<T>* pivotNode = getNode(splitIndex);

	//If the pivot node doesn't exist, then we cannot split.
	if(pivotNode == 0){
		return 0;
	}

	//Create the new half list.
	DoublyLinkedList<T>* half = new DoublyLinkedList<T>();

	//The capacity of the new list will remain the same,
	//while the size will equal the current size minus the
	//index. So a list of size 4, split at index 2, as in
	//the middle, will have a size of 2.
	half->capacity = this->capacity;
	half->size     = this->size - splitIndex;

	//The head of the half is the pivot node.
	half->head = pivotNode;

	//The tail of the half is the original tail.
	half->tail = this->tail;

	//The new tail of the original list will be the previous
	//element of the pivot node.
	this->tail = pivotNode->getPrevious();
	this->tail->setNext(0);
	this->size = splitIndex;


	return half;
}

template <class T>
Node<T>* DoublyLinkedList<T>::getNode(int index) {

	if(0 > index || index >= size){
		return 0;
	}

	Node<T>* currentNode = head;

	int i = 0;

	while(currentNode != 0){

		if(i == index)
			return currentNode;

		i++;

		currentNode = currentNode->getNext();
	}

	return 0;

}




template <class T>
Node<T>* DoublyLinkedList<T>::findNode(Node<T>* node){

	Node<T>* currentNode = head;

	while(currentNode != 0){

		if(currentNode == node)
			return currentNode;

		currentNode = currentNode->getNext();
	}

	return 0;
}

template <class T>
bool DoublyLinkedList<T>::nodeExists(Node<T>* node) {
	return findNode(node) != 0;
}

template <class T>
Node<T>* DoublyLinkedList<T>::findBySearchKey(int searchKey) {
	Node<T>* currentNode = head;

	while(currentNode != 0){

		if(searchKey < currentNode->getKey())
			return currentNode;

		currentNode = currentNode->getNext();
	}

	return 0;
}


template <class T>
Node<T>* DoublyLinkedList<T>::findKey(int key) {
	Node<T>* currentNode = head;

	while(currentNode != 0){

		if(currentNode->getKey() == key)
			return currentNode;

		currentNode = currentNode->getNext();
	}

	return 0;
}

template<class T>
bool DoublyLinkedList<T>::keyExists(int key) {
	return findKey(key) != 0;
}


template <class T>
void DoublyLinkedList<T>::print() {

	if(size == 0){
		cout << "Doubly Linked List is Empty. \n";
		return;
	}

	Node<T>* currentNode = head;

	printf("Head: %d | Tail: %d | Size: %d\n", head->getKey(), tail->getKey(), size);
	printf("------------------------------\n");
	T value;
	while(currentNode != 0){

		value = currentNode->getValue();
		printf("Key: %d \t Pointer: %p.\n", currentNode->getKey(), &value);

		currentNode = currentNode->getNext();
	}
	printf("------------------------------\n\n");

}


template <class T>
int DoublyLinkedList<T>::write(char* buffer, int offset){

	//Write the size of the current list as the first element of the buffer.
	memcpy(&buffer[offset], &size, sizeof(int));
	offset += sizeof(int);

	Node<T>* currentNode = head;

	while(currentNode != 0){
		offset = currentNode->write(buffer, offset);
		currentNode = currentNode->getNext();
	}

	return offset;
}

template <class T>
int DoublyLinkedList<T>::read(const char* buffer, int offset){

	int listSize;

	//Read in the stored size value.
	memcpy(&listSize, &buffer[offset], sizeof(int));
	offset += sizeof(int);

	//Return false on negative size.
	if(listSize < 0)
		return false;

	Node<T>* node;

	//Insert each node stored inside the buffer.
	for(int i = 0; i < listSize; i++){

		node = new Node<T>();

		offset = node->read(buffer, offset);

		insert(node);

	}

	return offset;
}

template<class T>
bool DoublyLinkedList<T>::isFull(){
	return capacity != 0 && capacity == size;
}

template<class T>
void DoublyLinkedList<T>::setCapacity(int capacity){
	this->capacity = capacity;
}

template <class T>
bool DoublyLinkedList<T>::empty(){

	Node<T>* currentNode = head;
	Node<T>* temp;

	while(currentNode != 0){
		temp = currentNode;
		delete temp;
		currentNode = currentNode->getNext();
	}

	head = 0;
	tail = 0;
	size = 0;

	return true;
}

template<class T>
inline Node<T>* DoublyLinkedList<T>::getHead() {
	return head;
}

template<class T>
inline Node<T>* DoublyLinkedList<T>::getTail() {
	return tail;
}

template<class T>
DoublyLinkedList<T>::~DoublyLinkedList() {

	empty();
}

#endif /* DOUBLYLINKEDLIST_C_ */







/**************************************************************/







#include "RecordFile.h"
#include "PageFile.h"


/**
 * BTLeafNode: The class representing a B+tree leaf node.
 */
class BTLeafNode {
  public:

	BTLeafNode();

	/**
	 * Mainly ensures that the allocated list is destroyed.
	 */
	virtual ~BTLeafNode();

	/**
	 * Prints the contents of the current node.
	 */
	void print();

	/**
	 * Returns true if the current length equals current capacity.
	 * False, otherwise.
	 */
	bool isFull();

	/**
	 * Sets the current working list. The previous list will not be
	 * valid or accessible.
	 */
	void setList(DoublyLinkedList<RecordId>* list);

   /**
    * Insert the (key, rid) pair to the node.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert
    * @param rid[IN] the RecordId to insert
    * @return 0 if successful. Return an error code if the node is full.
    */
    RC insert(int key, const RecordId& rid);

   /**
    * Insert the (key, rid) pair to the node
    * and split the node half and half with sibling.
    * The first key of the sibling node is returned in siblingKey.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert.
    * @param rid[IN] the RecordId to insert.
    * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
    * @param siblingKey[OUT] the first key in the sibling node after split.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC insertAndSplit(int key, const RecordId& rid, BTLeafNode& sibling, int& siblingKey);

	/**
	 * Find the index entry whose key value is larger than or equal to searchKey
	 * and output the eid (entry id) whose key value &gt;= searchKey.
	 * Remember that keys inside a B+tree node are sorted.
	 * @param searchKey[IN] the key to search for.
	 * @param eid[OUT] the entry number that contains a key larger
	 *                 than or equalty to searchKey.
	 * @return 0 if successful. Return an error code if there is an error.
	 */
	RC locate(int searchKey, int& eid);

	/**
 	 * Read the (key, rid) pair from the eid entry.
	 * @param eid[IN] the entry number to read the (key, rid) pair from
	 * @param key[OUT] the key from the slot
	 * @param rid[OUT] the RecordId from the slot
	 * @return 0 if successful. Return an error code if there is an error.
	 */
	RC readEntry(int eid, int& key, RecordId& rid);


   /**
    * Return the pid of the next slibling node.
    * @return the PageId of the next sibling node 
    */
    PageId getNextNodePtr();


   /**
    * Set the next slibling node PageId.
    * @param pid[IN] the PageId of the next sibling node 
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC setNextNodePtr(PageId pid);

   /**
    * Return the number of keys stored in the node.
    * @return the number of keys in the node
    */
    int getKeyCount();
 
   /**
    * Read the content of the node from the page pid in the PageFile pf.
    * @param pid[IN] the PageId to read
    * @param pf[IN] PageFile to read from
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC read(PageId pid, const PageFile& pf);
    
   /**
    * Write the content of the node to the page pid in the PageFile pf.
    * @param pid[IN] the PageId to write to
    * @param pf[IN] PageFile to write to
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC write(PageId pid, PageFile& pf);

  private:

   /**
    * The main memory buffer for loading the content of the disk page 
    * that contains the node.
    */
    char buffer[PageFile::PAGE_SIZE];

    DoublyLinkedList<RecordId>* list;

    PageId nextNodeId;

}; 


/**
 * BTNonLeafNode: The class representing a B+tree nonleaf node.
 */
class BTNonLeafNode {
  public:

	BTNonLeafNode();
	~BTNonLeafNode();
	void print();
	void setList(DoublyLinkedList<PageId>* list);

   /**
    * Insert a (key, pid) pair to the node.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert
    * @param pid[IN] the PageId to insert
    * @return 0 if successful. Return an error code if the node is full.
    */
    RC insert(int key, PageId pid);

   /**
    * Insert the (key, pid) pair to the node
    * and split the node half and half with sibling.
    * The sibling node MUST be empty when this function is called.
    * The middle key after the split is returned in midKey.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert
    * @param pid[IN] the PageId to insert
    * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
    * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey);

   /**
    * Given the searchKey, find the child-node pointer to follow and
    * output it in pid.
    * Remember that the keys inside a B+tree node are sorted.
    * @param searchKey[IN] the searchKey that is being looked up.
    * @param pid[OUT] the pointer to the child node to follow.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC locateChildPtr(int searchKey, PageId& pid);

   /**
    * Initialize the root node with (pid1, key, pid2).
    * @param pid1[IN] the first PageId to insert
    * @param key[IN] the key that should be inserted between the two PageIds
    * @param pid2[IN] the PageId to insert behind the key
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC initializeRoot(PageId pid1, int key, PageId pid2);

   /**
    * Return the number of keys stored in the node.
    * @return the number of keys in the node
    */
    int getKeyCount();

   /**
    * Read the content of the node from the page pid in the PageFile pf.
    * @param pid[IN] the PageId to read
    * @param pf[IN] PageFile to read from
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC read(PageId pid, const PageFile& pf);
    
   /**
    * Write the content of the node to the page pid in the PageFile pf.
    * @param pid[IN] the PageId to write to
    * @param pf[IN] PageFile to write to
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC write(PageId pid, PageFile& pf);

	/**
	 * Returns true if the current length equals current capacity.
	 * False, otherwise.
	 */
	bool isFull();

	PageId getPageIdAt(int index);

	PageId getNextNodePtr();
	PageId setNextNodePtr(PageId pid);
	int getMaxKey();

  private:

   /**
    * The main memory buffer for loading the content of the disk page 
    * that contains the node.
    */
    //Currently set 1024.
    char buffer[PageFile::PAGE_SIZE];

    DoublyLinkedList<PageId>* list;

    PageId nextNodeId;
}; 

#endif /* BTNODE_H */
